package junior.图;

public class 所有路径_图 {
    static int[][] check = {{0,0,0,0,1,0},
                            {0,1,0,0,1,0},
                            {0,1,0,0,0,0},
                            {0,0,0,1,0,0},
                            {0,1,0,1,0,0},
                            {0,0,1,0,1,0}};
    static int[][] direction = {{0,1},
                                {1,0},
                                {-1,0},
                                {0,-1}}; //右下左上
    static int m=6,n=6,count=0, minPath=100000,path=0;//m行n列
    public static void main(String[] args) {
        check[0][0]=2;
        recurision(0,0);
        System.out.println("count："+count);
        System.out.println("minPath："+minPath);
    }
    static void recurision(int x,int y){  // x 行 ， y 列
        path++;
        int newX,newY;
        // 结束条件
        if(x == n-1 && y == m-1){
            System.out.println("方案 "+(count+1)+" :***********************");
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(check[i][j] == 0)
                        System.out.print(0+" ");
                    else if(check[i][j] == 1)
                        System.out.print(1+" ");
                    else
                        System.out.print("*"+" ");
                }
                System.out.println();
            }
            minPath = Math.min(minPath,path);
            path = 0;
            count++;
            return;
        }
        // 深度优先搜索
        for (int i = 0; i < 4; i++) { // 遍历四个方向
            newX = x+direction[i][0];
            newY = y+direction[i][1];
            if( 0<=newX && newX< m && 0<=newY && newY<n){ // 判断：边界，是否为1（强）
                if((check[newX][newY] == 0)){
                    check[newX][newY] = 2; // 保存结果,check[][]值设置为2, 打标记
                    recurision(newX,newY); // 递归
                    check[newX][newY] = 0; // 取消标记(回溯：数据污染，原始数据多重复制)
                }
            }
        }
    }
}
